from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        map = {"2":["a","b","c"], 
        "3":["d","e","f"], 
        "4":["g","h","i"], 
        "5":["j","k","l"], 
        "6":["m","n","o"],
        "7":["p","q","r","s"], 
        "8":["t","u","v"], 
        "9":["w","x","y","z"]}
        res = []
        path = []
        if not digits:
            return res
        digits_list = list(digits)
        def dfs(index:int, path:List):
            if len(digits) == len(path):
                res.append("".join(path))
                return
            
            for d in map[digits_list[index]]:
                path.append(d)
                dfs(index+1, path)
                path.pop()
        dfs(0, path)
        return res

                
            

            
        